package com.leetcode.partition5;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/8/11 9:44
 */
public class LC474一和零 {

    public static int findMaxForm(String[] strs, int m, int n) {
        return dynamicProgramming(strs, m, n);
    }

    public static void main(String[] args) {
        String[] strs = {"0001", "10", "111001", "1", "0"};
        int m = 3, n = 2;
        System.out.println(findMaxForm(strs, m, n));
    }

    private static int dynamicProgramming(String[] strs, int m, int n) {
        //dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int zeroCount = 0, oneCount = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') zeroCount++;
                else oneCount++;
            }
            //需要给每一个符合条件的历史记录加1
            for (int i = m; i >= zeroCount; i--) {
                for (int j = n; j >= oneCount; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroCount][j - oneCount] + 1);
                }
            }
        }
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return dp[m][n];
    }
}
